package 蓝桥真题.javaB组国赛真题;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 迷宫 {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static final int N=2010;
    static int h[]=new int[N],e[]=new int[2*N],ne[]=new int[2*N],q[]=new int[N],d[][]=new int[N][N],n,m,idx;
    static int dix[]={-1,1,0,0},diy[]={0,0,-1,1};
    static void add(int a,int b){
        e[idx]=b;ne[idx]=h[a];h[a]=idx++;
    }
    static void bfs(){
        for (int i = 0; i <n ; i++)
            Arrays.fill(d[i],0x7f7f7f7f);//将各个点到终点的最短距离初始化为正无穷
        d[n-1][n-1]=0;//终点到终点的最短距离为0
        int tt=-1,hh=0;//初始化队列
        q[++tt]=(n-1)*n+n-1;//将终点放入队列
        while(hh<=tt){
            int t=q[hh++];
            int x=t/n,y=t%n;
            for(int i=0;i<4;i++){
                int tx=x+dix[i],ty=y+diy[i];
                if(tx>=0&&tx<n&&ty>=0&&ty<n){
                    if(d[x][y]+1<d[tx][ty]){
                        d[tx][ty]=d[x][y]+1;
                        q[++tt]=tx*n+ty;//被更新的点入队
                    }
                }
            }
            for(int i=h[t];i!=-1;i=ne[i]){//遍历该点的传送门 更新最短距离
                int j=e[i];
                int tx=j/n,ty=j%n;
                if(d[x][y]+1<d[tx][ty]){
                    d[tx][ty]=d[x][y]+1;
                    q[++tt]=j;//被更新的点入队
                }
            }
        }
    }
    public static void main(String[] ss) throws IOException {
        ss=br.readLine().split(" ");
        n=Integer.parseInt(ss[0]);m=Integer.parseInt(ss[1]);
        Arrays.fill(h,-1);
        while(m-->0){
            ss=br.readLine().split(" ");
            int x1=Integer.parseInt(ss[0])-1,y1=Integer.parseInt(ss[1])-1,x2=Integer.parseInt(ss[2])-1,y2=Integer.parseInt(ss[3])-1;
            int a=x1*n+y1,b=x2*n+y2;//将二维展开到一维
            add(a,b);add(b,a);//建立双向传送门
        }
        bfs();//使用bfs求出最短路
        int res=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                res+=d[i][j];
        System.out.printf("%.2f", (res * 1.0) / (n * n));
    }
}
/*
2 1
1 1 2 2
* */